<!DOCTYPE html>

<html lang="zh-CN">

<head>
  
  <title>堆栈 - lingqu&#39;blog</title>
  <meta charset="UTF-8">
  <meta name="description" content="">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5">
  
  

  <link rel="shortcut icon" href="/favicon.ico" type="image/png" />
  <meta name="description" content="概念 插入数据：入栈（Push）  删除数据：出栈（Pop）  后入先出：Last In First Out（LIFO）">
<meta property="og:type" content="article">
<meta property="og:title" content="堆栈">
<meta property="og:url" content="https://lingqu.github.io/2021/05/16/Stack/index.html">
<meta property="og:site_name" content="lingqu&#39;blog">
<meta property="og:description" content="概念 插入数据：入栈（Push）  删除数据：出栈（Pop）  后入先出：Last In First Out（LIFO）">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://lingqu.github.io/2021/05/16/Stack/Snipaste_2021-05-15_20-59-10.png">
<meta property="og:image" content="https://lingqu.github.io/2021/05/16/Stack/Snipaste_2021-05-15_21-25-59.png">
<meta property="article:published_time" content="2021-05-16T11:35:57.000Z">
<meta property="article:modified_time" content="2021-05-27T14:25:38.328Z">
<meta property="article:author" content="lingqu">
<meta property="article:tag" content="数据结构">
<meta property="article:tag" content="C++">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://lingqu.github.io/2021/05/16/Stack/Snipaste_2021-05-15_20-59-10.png">
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/combine/npm/highlight.js@9.15.8/styles/atom-one-dark.css,npm/justifiedGallery@3.8.1/dist/css/justifiedGallery.min.css,gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css,npm/hexo-theme-nexmoe@latest/source/lib/mdui_043tiny/css/mdui.css,npm/hexo-theme-nexmoe@latest/source/lib/iconfont/iconfont.css?v=233" crossorigin>
  <link rel="stylesheet" href="/css/style.css?v=1629344957176">
  
  <link rel="stylesheet" href="/css/style.css?v=1629344957176">
  <link rel="stylesheet" href="/lib/iconfont/iconfont.css?v=1629344957176">
<meta name="generator" content="Hexo 5.4.0"></head>

<body class="mdui-drawer-body-left">
  
  <div id="nexmoe-background">
    <div class="nexmoe-bg" style="background-image: url(http://pic1.win4000.com/wallpaper/f/5922779a761cd.jpg)"></div>
    <div class="mdui-appbar mdui-shadow-0">
      <div class="mdui-toolbar">
        <a mdui-drawer="{target: '#drawer', swipe: true}" title="menu" class="mdui-btn mdui-btn-icon mdui-ripple"><i class="mdui-icon nexmoefont icon-menu"></i></a>
        <div class="mdui-toolbar-spacer"></div>
        <!--<a href="javascript:;" class="mdui-btn mdui-btn-icon"><i class="mdui-icon material-icons">search</i></a>-->
        <a href="/" title="lingqu" class="mdui-btn mdui-btn-icon"><img src="https://inews.gtimg.com/newsapp_bt/0/13492515314/1000" alt="lingqu"></a>
       </div>
    </div>
  </div>
  <div id="nexmoe-header">
      <div class="nexmoe-drawer mdui-drawer" id="drawer">
    <div class="nexmoe-avatar mdui-ripple">
        <a href="/" title="lingqu">
            <img src="https://inews.gtimg.com/newsapp_bt/0/13492515314/1000" alt="lingqu" alt="lingqu">
        </a>
    </div>
    <div class="nexmoe-count">
        <div><span>文章</span>8</div>
        <div><span>标签</span>3</div>
        <div><span>分类</span>0</div>
    </div>
    <div class="nexmoe-list mdui-list" mdui-collapse="{accordion: true}">
        
        <a class="nexmoe-list-item mdui-list-item mdui-ripple" href="/" title="回到首页">
            <i class="mdui-list-item-icon nexmoefont icon-home"></i>
            <div class="mdui-list-item-content">
                回到首页
            </div>
        </a>
        
        <a class="nexmoe-list-item mdui-list-item mdui-ripple" href="/about.html" title="关于博客">
            <i class="mdui-list-item-icon nexmoefont icon-info-circle"></i>
            <div class="mdui-list-item-content">
                关于博客
            </div>
        </a>
        
        <a class="nexmoe-list-item mdui-list-item mdui-ripple" href="/PY.html" title="我的朋友">
            <i class="mdui-list-item-icon nexmoefont icon-unorderedlist"></i>
            <div class="mdui-list-item-content">
                我的朋友
            </div>
        </a>
        
    </div>
    <aside id="nexmoe-sidebar">
  
  <div class="nexmoe-widget-wrap">
    <div class="nexmoe-widget nexmoe-search">
        <form id="search_form" action_e="https://cn.bing.com/search?q=site:nexmoe.com" onsubmit="return search();">
            <label><input id="search_value" name="q" type="search" placeholder="搜索"></label>
        </form>
    </div>
</div>
  
  <div class="nexmoe-widget-wrap">
    <div class="nexmoe-widget nexmoe-social">
        <a class="mdui-ripple" href="https://jq.qq.com/?_wv=1027&k=5CfKHun" target="_blank" mdui-tooltip="{content: 'QQ群'}" style="color: rgb(249, 174, 8);background-color: rgba(249, 174, 8, .1);">
            <i class="nexmoefont icon-QQ"></i>
        </a><a class="mdui-ripple" href="https://space.bilibili.com/51207190" target="_blank" mdui-tooltip="{content: '哔哩哔哩'}" style="color: rgb(231, 106, 141);background-color: rgba(231, 106, 141, .15);">
            <i class="nexmoefont icon-bilibili"></i>
        </a><a class="mdui-ripple" href="https://github.com/lingqu/" target="_blank" mdui-tooltip="{content: 'GitHub'}" style="color: rgb(25, 23, 23);background-color: rgba(25, 23, 23, .15);">
            <i class="nexmoefont icon-github"></i>
        </a>
    </div>
</div>
  
  

  
  
  <div class="nexmoe-widget-wrap">
    <div id="randomtagcloud" class="nexmoe-widget tagcloud nexmoe-rainbow">
      <a href="/tags/C/" style="font-size: 20px;">C++</a> <a href="/tags/JavaScript/" style="font-size: 10px;">JavaScript</a> <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" style="font-size: 20px;">数据结构</a>
    </div>
    
  </div>

  
</aside>
    <div class="nexmoe-copyright">
        &copy; 2021 lingqu
        Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
        & <a href="https://github.com/theme-nexmoe/hexo-theme-nexmoe" target="_blank">Nexmoe</a>
        
    </div>
</div><!-- .nexmoe-drawer -->
  </div>
  <div id="nexmoe-content">
    <div class="nexmoe-primary">
        <div class="nexmoe-post">

  <article>
    
        <div class="nexmoe-post-cover" style="padding-bottom: 45.83333333333333%;"> 
            <img data-src="http://pic1.win4000.com/wallpaper/f/5922779a761cd.jpg" data-sizes="auto" alt="堆栈" class="lazyload">
            <h1>堆栈</h1>
        </div>
    
    
    <div class="nexmoe-post-meta nexmoe-rainbow" style="margin:10px 0!important;">
    <a><i class="nexmoefont icon-calendar-fill"></i>2021年05月16日</a>
    <a><i class="nexmoefont icon-areachart"></i>259 字</a>
    <a><i class="nexmoefont icon-time-circle-fill"></i>大概 1 分钟</a>
</div>

    

    <h2 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h2><ul>
<li><p>插入数据：入栈（Push）</p>
</li>
<li><p>删除数据：出栈（Pop）</p>
</li>
<li><p>后入先出：Last In First Out（LIFO）</p>
<span id="more"></span></li>
</ul>
<p><img data-fancybox="gallery" data-sizes="auto" data-src="Snipaste_2021-05-15_20-59-10.png" alt="art" class="lazyload"></p>
<h2 id="主要操作"><a href="#主要操作" class="headerlink" title="主要操作"></a>主要操作</h2><p>储存结构通常由一个一维数组和一个记录栈顶元素位置的变量组成</p>
<h3 id="入栈"><a href="#入栈" class="headerlink" title="入栈"></a>入栈</h3><pre><code class="c++">#define MaxSize &lt;最大元素个数&gt;
struct SNode&#123;
   ElementType Data[MaxSize];  
    int Top;
&#125;;
void Push(SNode* PtrTop,Element item)
&#123;
    if(PtrTop-&gt;Top==MaxSize-1)&#123;
        cout &lt;&lt; &quot;堆栈满&quot;;
        return ;
    &#125;else&#123;
        PtrTop-&gt;Data[++(PtrTop-&gt;Top)]=item;
        return ;
    &#125;
&#125;
</code></pre>
<h3 id="出栈"><a href="#出栈" class="headerlink" title="出栈"></a>出栈</h3><pre><code class="c++">ElementType Pop(SNode* PtrTop)
&#123;
    if(PtrTop=-1)&#123;
        cout &lt;&lt; &quot;栈为空&quot;;
        return ;
    &#125;
    else 
        return (PtrTop-&gt;Data[PtrTop-&gt;Top--]);
&#125;
</code></pre>
<h2 id="链表实现堆栈"><a href="#链表实现堆栈" class="headerlink" title="链表实现堆栈"></a>链表实现堆栈</h2><p>栈的链式存储结构实际上是一个单链表，叫做链栈。</p>
<p>Top在链表头上。</p>
<p><img data-fancybox="gallery" data-sizes="auto" data-src="Snipaste_2021-05-15_21-25-59.png" alt="art" class="lazyload"></p>
<pre><code class="c++">struct SNode
&#123;
    ElementType Data;
    SNode* next;
&#125;;
//构建一个堆栈的头结点，返回指针
SNode* CreateStack()
&#123;
    SNode *PtrTop;
    PtrTop=(SNode*)new SNode;
    PtrTop-&gt;next=NULL;
    return PtrTop;
&#125;
//判断堆栈是否为空
SNode* IsEmpty(SNode PtrTop)
&#123;
    return (PtrTop-&gt;next == NULL);
&#125;
</code></pre>
<h3 id="入栈-1"><a href="#入栈-1" class="headerlink" title="入栈"></a>入栈</h3><pre><code class="c++">void Push(ElementType item,SNode* PtrTop)
&#123;
    SNode* p;
    p=(SNode*)new SNode;
    p-&gt;next=PtrTop-&gt;next;
    p-&gt;Data=item;
    PtrTop-&gt;next=p;
&#125;
</code></pre>
<h3 id="出栈-1"><a href="#出栈-1" class="headerlink" title="出栈"></a>出栈</h3><pre><code class="c++">ElemtType Pop(SNode* PtrTop)
&#123;
    SNode* FirstCell;
    ElementType TopElem;
    if(IsEmpty(PtrTop))&#123;
        cout &lt;&lt; &quot;堆栈为空&quot;;
        return NULL;
    &#125;else&#123;
        FirstCell=PtrTop-&gt;Next;
        PtrTop-&gt;next=FirstCell-&gt;next;
        TopElem = FirstCell-&gt;Data;
        delete FirstCell;
        return TopElem;
    &#125;
&#125;
</code></pre>

  </article>

  
    
  <div class="nexmoe-post-copyright">
    <strong>本文作者：</strong>lingqu<br>
    <strong>本文链接：</strong><a href="https://lingqu.github.io/2021/05/16/Stack/" title="https:&#x2F;&#x2F;lingqu.github.io&#x2F;2021&#x2F;05&#x2F;16&#x2F;Stack&#x2F;" target="_blank" rel="noopener">https:&#x2F;&#x2F;lingqu.github.io&#x2F;2021&#x2F;05&#x2F;16&#x2F;Stack&#x2F;</a><br>
    
      <strong>版权声明：</strong>本文采用 <a href="https://creativecommons.org/licenses/by-nc-sa/3.0/cn/deed.zh" target="_blank">CC BY-NC-SA 3.0 CN</a> 协议进行许可
    
  </div>


  
  
  <div class="nexmoe-post-meta nexmoe-rainbow">
    
    
        <a class="nexmoefont icon-tag-fill -none-link" href="/tags/C/" rel="tag">C++</a> <a class="nexmoefont icon-tag-fill -none-link" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag">数据结构</a>
    
</div>

  <div class="nexmoe-post-footer">
    <section class="nexmoe-comment">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.min.css">
<div id="gitalk"></div>
<script src="https://cdn.jsdelivr.net/npm/gitalk@1.5.0/dist/gitalk.min.js"></script>
<script type="text/javascript">
    var gitalk = new Gitalk({
        clientID: '80b2453b6d5f37ad6225',
        clientSecret: '43e99fa852795c9a7b3eb924b2558c64b84bbdeb',
        id: window.location.pathname,
        repo: 'nexmoe.github.io',
        owner: 'nexmoe',
        admin: 'nexmoe'
    })
    gitalk.render('gitalk')
</script>
</section>
  </div>
</div>
        <div class="nexmoe-post-right">
          <div class="nexmoe-fixed">
            <div class="nexmoe-tool"> 
              
                
              
              <a href="#nexmoe-content" class="toc-link" aria-label="回到顶部" title="top"><button class="mdui-fab mdui-ripple"><i class="nexmoefont icon-caret-top"></i></button></a>
            </div>
          </div>
        </div>
    </div>
  </div>
  <script src="https://cdn.jsdelivr.net/combine/npm/lazysizes@5.1.0/lazysizes.min.js,gh/highlightjs/cdn-release@9.15.8/build/highlight.min.js,npm/mdui@0.4.3/dist/js/mdui.min.js?v=1"></script>
<script>
	hljs.initHighlightingOnLoad();
</script>

<script src="https://cdn.jsdelivr.net/npm/jquery@3.5.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>


<script src="https://cdn.jsdelivr.net/gh/xtaodada/xtaodada.github.io@0.0.2/copy.js"></script>
 

<script src="/js/app.js?v=1629344957177"></script>

<script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.8.1/dist/js/jquery.justifiedGallery.min.js"></script>
<script>
	$(".justified-gallery").justifiedGallery({
		rowHeight: 160,
		margins: 10,
	});
</script>

  





</body>

</html>
